//题目:
// 泰波那契序列 Tn 定义如下： 
// T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
// 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
#include<iostream>
#include<vector>

using namespace std;
//代码:
class Solution 
{
public:
    int tribonacci(int n) 
    {
        // //1.状态表示:dp[i]=Ti
        // vector<int> dp(n+1);
        // //2.状态转移方程: dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

        // //3.处理边界问题
        // if(n==0)return 0;
        // if(n==1 || n==2)return 1;

        // dp[0]=0,dp[1]=dp[2]=1;

        // //4.初始化dp数组
        // for(int i=3;i<=n;i++)
        //     dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

        // return dp[n];

        //空间优化————滚动数组
        //1.状态表示:dp[i]=Ti
        int tmp1=0,tmp2=1,tmp3=1,res;
        //2.状态转移方程: res=tmp1+tmp2+tmp3

        //3.处理边界问题
        if(n==0)return 0;
        if(n==1 || n==2)return 1;

        //4.初始化dp数组
        for(int i=3;i<=n;i++)
        {
            res=tmp1+tmp2+tmp3;
            tmp1=tmp2;
            tmp2=tmp3;
            tmp3=res;
        }

        return res;
    }
};